package projectEuler.net;
/**
 * This class generates prime numbers up to user specified maximum
 * The algorithm used is the Sieve of Eratosthenes. Given an array
 * of integers starting at 2: Find the first uncrossed inter, and
 * cross out all its multiples. Repeat until the first uncrossed
 * integer exceeds the square root of the maximum value
 * 
 * @author xrose
 *
 */
public class PrimesGenerator {
	private static boolean[] unCrossed;
	private static int[] result;
	
	/**
	 * @param maxValue
	 */
	public static int[] generatePrimes(int maxValue){
		if(maxValue<2) return new int[0];
		initializeArrayOfIntegers(maxValue);
		crossOutMultiples();
		loadPrimes();
		return result;
	}
	public static boolean[] genPrimes(int maxValue){
		if(maxValue<2) return new boolean[]{false};
		initializeArrayOfIntegers(maxValue);
		crossOutMultiples();
		return unCrossed;
	}
	/**
	 * @
	 */
	private static void loadPrimes(){
		int i, j;
		int count =0;
		//how many primes are there
		for(i=0; i<unCrossed.length; i++)
			if(unCrossed[i]) count++;
		result = new int[count];
		//move the primes into the result
		for(i=0, j=0; i<unCrossed.length; i++)
			if(unCrossed[i]) result[j++] = i;
	}
	private static void crossOutMultiples(){
		int i, j;
		for(i=2; i<Math.sqrt(unCrossed.length); i++)
			if(unCrossed[i])
				for(j=2*i; j<unCrossed.length; j+=i) unCrossed[j]=false;
	}
	private static void initializeArrayOfIntegers(int maxValue){
		unCrossed=new boolean[maxValue+1];
		//init array to true
		for(int i=0; i<unCrossed.length; i++) unCrossed[i] = true;
		unCrossed[0]=unCrossed[1]=false;
	}
}